#include "myheap.h"

namespace sk {

MyHeapImp::MyHeapImp() {
    length = 0;
}

void MyHeapImp::heapifyDown(int i) {
    if (i < 1 || i > length) return;

    int l = left(i);
    if (l < 1 || l > length) l = -1;

    int r = right(i);
    if (r < 1 || r > length) r = -1;

    int v = arr[i];
    int lv = -1; if (l != -1) lv = arr[l];
    int rv = -1; if (r != -1) rv = arr[r];

    if (lv == -1 && rv == -1) return;
    else if (lv != -1 && rv != -1 && (v > lv || v > rv)) {
        if (lv >= rv) {
            mySwap(&arr, i, r);
            heapifyDown(r);
        } else {
            mySwap(&arr, i, l);
            heapifyDown(l);
        }
    } else if (lv != -1 && v > lv) {
        mySwap(&arr, i, l);
        heapifyDown(l);
    } else if (rv != -1 && v > rv) {
        mySwap(&arr, i, r);
        heapifyDown(r);
    }
}

void MyHeapImp::heapifyUp(int index) {
    while (arr[parent(index)] >= arr[index] && index > 1) {
        mySwap(&arr, index, parent(index));
        index = parent(index);
    }
}

int MyHeapImp::parent(int index) {
    return index / 2;
}

int MyHeapImp::left(int index) {
    return index * 2;
}

int MyHeapImp::right(int index) {
    return index * 2 + 1;
}

int MyHeapImp::getMin() {
    return arr[1];
}

int MyHeapImp::extractMin() {
    int result = arr[1];

    mySwap(&arr, 1, length - 1);
    heapifyDown(1);

    return result;
}

void MyHeapImp::insert(int value) {
    arr.add(value);
    length++;

    heapifyUp(length - 1);
}

void MyHeapImp::buildHeap(const MyArray& arr) {
    this->arr = arr;
//    printf("arrSize: %d\n", this->arr.getSize());
    length = this->arr.getSize() - 1;

    for (int i = length; i > 0; i--) {
//        printf("buildheap: ");
//        print();
//        printf("\n");

        heapifyDown(i);
    }
}

int MyHeapImp::size() {
    return length;
}

void MyHeapImp::print() {
    for (int i = 1; i <= length; i++) {
        printf("%d ", arr[i]);
    }
}

void heapsort(int* arr, int length) {
    MyHeapImp heap;
    heap.buildHeap(MyArray(arr, length));

    for (int i = heap.length; i > 0; i--) {
//        printf("**\n");
//        heap.print();
//        printf("\n");
        mySwap(&heap.arr, 1, i);
        heap.length--;
        heap.heapifyDown(1);
    }

    for (int i = 0; i < length; i++) {
        printf("%d ", arr[i]);
    }
}

}
